COMMENT ⊗   VALID 00011 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002
C00005 00003		It is assumed here that decisions are made at each level on the
C00010 00004
C00014 00005		By a protraction schedule we mean a list, for all legs of the
C00019 00006
C00024 00007
C00030 00008		Note that the track schedule is not the same as the protraction
C00035 00009		Gait symmetry imposes a restriction on the mutual leg phasing,
C00041 00010
C00046 00011		Suppose that the length of the protraction phase is the same for all
C00048 ENDMK
C⊗;

	COMPUTER SIMULATION OF THE MOTION OF A WALKING DEVICE

				by

     D.C. Okhotsimskii, A.K. Platonov, G.K. Borovin, I.I. Karpov




Abstract
--------

	The subject of this paper is a multilevel adaptive algorithm
for controlling the motion of a six-legged automatic device capable
of traveling over an irregular surface.  Computer simulation is
carried out.  A stylized picture of the locomotion of the device,
obtained on the computer display, makes it possible to judge the
efficiency of the proposed algorithms.



			- - - - - - - - - -


	Recent years have witnessed ever-increasing interest in the
creation of automatic walking systems.  A device moving with the aid
of its extremities possesses, in principle, a high degree of
adaptability to terrain and, in motion under difficult conditions,
achieves a degree of comfort and navigability inaccessible, say,
to wheeled and tracked systems.  These advantages of walking
devices have long been known.  One of the principal obstacles to
their development has been the difficulty of creating a control
system able to stabilize the device and coordinate its extremities
in motion over irregular surfaces.  Recent progress in small digital
computers offers hope for the realization of control algorithms
capable of solving the highly complex problem of the motion of a
walking device.  The development of such algorithms is now a pressing
problem.

	The most advantagious design for control of a walking device
would seem to be multilevel hierarchic structure.  The sequence of
levels required, beginning with the lowest, is approximately as
follows:

	control of the motion of a single extremity;
	coordination of extremities;
	positioning of legs;
	selection of law of motion of body;
	selection of track of motion over terrain.

	It is assumed here that decisions are made at each level on the
basis of information acquired previously from higher levels, results of
measurements made at the present level, and messages received from
lower levels.

	Computer simulation is an effective tool in the design of control
algorithms for walking systems.  One can input to the computer a model
of the device, a model of the external medium, and the control algorithm,
detailed as necessary at each stage of design, and study the functioning
of the system.  In this context, illuminated display of the locomotion
of the system on a screen proves extremely useful.  Observing the picture
of the system's motion, one can gain a fairly clear idea of the
functioning of the system or of the specific level or group of levels
being worked out.

	The present paper is concerned with that part of the control
algorithm extending from information about the topography of the
terrain to programmed kinematics of the motion of the extremities.  We
shall also briefly discuss selection of the type and geometry of
extremities and joints best suited for adaptability to terrain and
convenient for solution of the diverse problems of motion, both on course,
when the device is coping with topographies of varying degrees of
difficulty, and when it is overcoming certain types of local obstacle.

	At the first stage of our work, whose aim was in the main
methodological, we considered a fairly simple model of the walking
device.  It is assumed that the body of the device moves uniformly and
rectilinearly along a surface whose irregularity is relatively low
and within the adaptive capacity of the legs.  The device has six
identical legs attached along the body, three on each side.  Each leg
consists of a thigh and a shank and has two degrees of freedom, one in
the shank and one at the hip joint (point of suspension from the body);
it cn move in the vertical plane containing the body's direction of
motion.

	The model is capable of locomotion, using several types of
regular gait.  In motion, the vertical coordinate of the point at
which the leg is put down adapts to the terrain.  It is assumed that
all information concerning the terrain is available to the device.

	At the second stage we investigated a more sophisticated model,
capable of solving more complex problems of motion.  As in the first
model, the six identical legs consist of two componen4ts, thigh and shank. 
The hip joint is a hinge with two degrees of freedom.  When the body is
horizontal, the first axis of this hinge is vertical and the second
horizontal, parallel to the axis of the shank hinge.  With this choice
of axes, both components of the leg remain in the vertical plane
throughout.  During motion, the plane of the leg changes position,
rotating about the vertical axis at the hip joint.

	Control algorithms for motion of the second model were
investigated at the first two of the levels listed above.  It was
assumed that the motion of the body and the track to be followed are
given.  The algorithm selected suitable times for each leg to be
lowered and lifted from the surface, and modeled the protractive
motion of the leg in accordance with the topography.

	The results of our investigation, for both the first and the
second model, were filmed from the computer display, providing an
idea of the efficiency of our technique.



I.	GAIT OF WALKING DEVICE AND STABILITY

	In this section we give a kinematic description of the gait
of the walking device and criteria for its stability.  Concepts and
definitions needed later are introduced.  The results of /5 - 16/ are
used.
	Consider the simplest type of motion of a walking device: the
body moves uniformly and rectilinearly on a horizontal plane, which
supports the device during motion.

	The motion of each leg consists of a sequence of stepping
cycles,  each of which in turn consists of a retraction phase and a
protraction phase.  We assume that the gait is based on a standard
time cycle of retraction and protraction, in other words, the retraction
time and protraction time, hence also the entire length of the cycle,
remain constant for each leg  from step to step and are the same for all
legs.

We introduce a coordinate system Oxy rigidly attached to the body of
the device.  The origin  of the system coincides with the center of
gravity of the body, the axis Ox points forward along the
longitudinal axis of the device in the direction of motion, and the
axis Oy is perpendicular to Ox, pointing to the left of the motion.
Let x↓0,y↓0 be the coordinated of the hip joint when the device is
placed on the supporting plane.  The relative coordinates of the hip
joint will in general vary from step to step.  We stipulate a stepping
regime in which the relative coordinates of the hip joint remain
constant for all stepping cycles of the leg.

The gait of the walking device is said to be regular if the motion of
all legs is governed by a standard retraction-protraction cycle and the
relative coordinates y↓0,y↓0 of the hip joints of all legs remain
constant from step to step.
	By a protraction schedule we mean a list, for all legs of the
device, of the instants at which they are lifted from the support plane
and the instants at which they are put down.  A protraction schedule is
said to be regular if the motion of the legs is defined by a regular
cycle.  A protraction schedule for a regular gait is regular.

	Let the schedule be regular, and consider the lifting instant
of some leg.  The next lifting instant for the same leg occurs after
a time interval equal to the length of the standard cycle.  The
lifting instants of all the other legs are distributed in some way
over this time interval.  As parameters of this distribution we take
the times elapsing from the beginning of the interval to the lifting
instants of the respective legs.  The number of essential parameters
of this kind is the total number of legs minus one, since the reference
point is the lifting instant of one of the legs, so that one of the
parameters is always zero.  We call these parameters mutual leg-
phasing parameters.  A regular schedule is completely determined by the
length of the cycle, the protraction time and the mutual leg-phasing.

	Above we considered the coordinates y↓0,y↓0, which,characterize
the position of hip joint on the body of the device at the instant of
contact with the supporting plane.   The process involved in the
retraction phase consists in keeping y constant and decreasing x.
During the retraction phase, the supporting point of the leg in the
system Oxy rigidly attached to the body of the device is uniformly
displaced along a segment parallel to the direction of motion.  We
call this the supporting segment of the leg.  The length of the
supporting segment will be called the constructive span.  It is obvious
that the constructive span is equal to the distance through which the
body moves during the retraction phase.

	The constructive span is a constructive parameter, characterizing
the longitudinal displacement of the hip joint.  In a regular gait the
constructive span does not vary from cycle to cycle and is the same for
all legs.

	We now consider the set of track points on the supporting plane,
i.e., the points at which the leg is set down during the stepping
process; we call this the track sequence of the leg.

	In regular gait, for motion over a plane, the points of the track
sequence lie on a straight line parallel to the direction of motion and
are uniformly positioned on this line, at equal intervals.  The length
of the interval will be called the track span.  The length of the track
span is equal to the distance through which the body moves during a
standard cycle.  The track sequences of different legs are identical
and may be made to coincide by a parallel translation.  The track span
exceeds the constructive span by the longitudinal displacement of the
device during the protraction phase.


	The set of track sequences of the legs forms the track.  The track
of a walking device moving with a regular gait will be called a regular
track.  In this case (uniform and rectilinear motion parallel to the
horizontal supporting plane), a regular track is a collection of point
sequences on parallel straight lines, arranged on these lines at constant
intervals, the same for all lines.

	One possible regime for the device is "step by step" motion, in
which the legs on either side of the device make contact with the
supporting plane at points of the same track sequence.  In this case the
track will consist of two track sequences, one for the legs on each side
of the device, left and right.

	If the points of contact are marked on the supporting plane, the
track is represented by a set of track points which remain on the plane
after passage of the device.  However, our terms "track sequence" and
"track" may also be used in relation to future points of contact.
Thus, in the sequel we shall speak of motion over a given track,
understanding thereby that the device must use certain well-defined,
prescribed points of contact on the supporting plane.

	We now consider the stability problem.  Consider the points of
contract of the legs on the supporting plane at some instant of time, and
construct their convex hull.  We call this the supporting polygon or
supporting contour.  The condition for static stability of the device is
that the line of action of the weight of the device must cut the supporting
plane within the supporting contour.  Gaits for which this condition holds
throughout motion will be called stable gaits.

	A necessary condition for a gait to be stable is that at least
three legs be in the retraction phase at any time during motion.  It
follows that the minimum number of legs for which the device will possess
a statically stable gait is four.  In a statically stable gait of a
four-legged system, only one leg may be in the protraction phase.  The legs
move in sequence, one after the other.  No leg is lifted from the
supporting plane before the previous leg has been set down.  In devices
with more than four legs the protraction phases may overlap, and these
devices may possess gaits of types other than the sequential gait just
described.

	The static stability condition is a necessary and sufficient
condition for stability of a device at rest on the supporting plane.
An analogous kinetostatic stability condition may be formulated for a
moving device.  The condiion is that throughout motion the torques produced
by the forces of gravity and of inertia acting on the body and legs of the
device relative to each side of the supporting contour must tend to turn
the device into the supporting contour.  If these forces are reduced to
their resultant, this condition means that at any instant during the motion
the resultant should pass within the supporting contour.  If the body is
moving uniformly and rectilinearly, it has no forces of inertia.


	The kinetostatic stability condition is completely rigorous but
its use requires computation of inertial forces.  If the body's motion is
sufficiently smooth and the masses of the legs and resulting inertial
forces in motion sufficiently small, it is more convenient to use an
approximate criterion, according to which the resultant of the forces
of gravity acting on the body must remain within the supporting contour.
This criterion is rigorous if the legs have no mass and the body is at
rest or moving uniformly and rectilinearly, and also when the body is
moving forward at a velocity whose horizontal component is constant in
magnitude and direction.  In the latter case the resultant of the forces of
inertia is vertical and passes through the center of mass of the body.
In the sequenl, unless otherwise stated, the term "static stability" will
refer to this approximate criterion.

	For correct utilization of the approximate stability criterion,
we find it expedient to introduce the concept of the "static stability"
reserve.  Let the projection of the device's center of mass on the
supporting plane lie inside the supporting polygon.  We define the static
stability reserve to be the minimum distance of the projection of the
center of mass from the sides of the supporting polygon at the instant
in question.  The static stability reserve will vary during motion.
When designing the kinematics of a walking device, one must ensure that the
static stability reserve remain throughout motion above a certain minimal
value, which must be suitably chosen for the device in question by
estimating the contribution of the inertial forces and the influence of the
perturbing forces and effects produced by possible deviations of the motion
of body and legs from the prescribed motion.

	Static stability of the device depends on the relative positions
of the center of mass and the supporting contour during motion.  When the
legs are protracting the supporting contour varies, and in order to
compute it one must know the position of the points of contact of the legs
which are in the retraction phase.

	We define a track schedule of a leg to be a list of the initial
and final instants of contact of the leg with each point of its track
sequence.  Track schedules are drawn up for individual legs together
with the track schedule for the whole device.  The supporting contour
of the device at each instant of time is fully determined by the track
and the track sequence.

	Each supporting contour subsists for a certain time, during which
(assuming stability) the projection of the center of mass is inside the
contour, moving in the direction of motion of the device.  If the center
of mass moves along a straight line, its projection will move inside the
supporting contour along a segment whose initial point corresponds to
the instant at which the contour is formed, its final point to the time at
which the contour is readjusted.  Since the supporting contour is convex,
no interior point of this segment can approach closer to a point of the
contour than its initial and final points.  This means that the reference
instants for computation of the static stability reserve are the instants
at which the legs are lifted and lowered.
	Note that the track schedule is not the same as the protraction
schedule considered previously, since the former indicates ot only the
initial and final instants of the retraction phase for each leg but also
records the point of the track sequence with which the leg must make
contact.

	We shall study the motion of a six-legged walking device.  We
assume that the legs are symmetrically positioned on the body, three
along each side (Fig. 1).  In Fig. 1, R↓1,R↓2,R↓3 denote the hip joints of
the foreleg, miiddleleg and hindleg on the right, L↓1,L↓2,L↓3 the
corresponding hip joints on the left.  To simplify matters, we assume that
the legs possess identical geometric and kinematic parameters.

	We need parameters to characterize the position of the point of
contact of a leg relative to its hip joint.  Let us define the anterior
stagger to be the distance, in the direction of the longitudinal axis of
the device, between the point of contact of the leg at the instant it is
put down and the hip joint.  The anterior stagger is equal to the difference
between the x-coordinates of the two relevant points.  It is assumed
positive if the point of contact leads the hip joint.


		- - - - - - - - - - - - - - - -

		    Fig. 1 [on Russian p. 14]

		- - - - - - - - - - - - - - - -


	The posterior stagger is defined similarly, for the instant at
which the leg is lifted.  The posterior stagger is assumed positive if the
point of contact lags the hip joint.  The sum of the anterior and posterior
staggers is equal to the length of the supporting segment, i.e., the
constructive span.

	We define the lateral stagger to be the lateral distance between
the point of contact and the hip joint.  The lateral stagger is assumed
positive if the point of contact is farther from the longitudinal axis than
the hip joint.  If the motion of the body is rectilinear, the lateral
stagger is constant during the retraction phase and does not vary from
step to step if the gait is regular.  In the simplest organization of leg
kinematics the lateral stagger is the same for all legs on each side.

	The symmetrical positions of the legs along the body make it
natural to devote special attention to symmetrical gaits.  Call a regular
gait symmetrical if, after a time equal to half the length of the
standard cycle, the postures of the legs are symmetrical to the original
ones with respect to the longitudinal axis of the device.  In walking
devices, symmetry of this type is an expression of the equal functions
of the right and left rows of legs, and is the natural choice, for
example, when the device is moving on a horizontal surface.
	Gait symmetry imposes a restriction on the mutual leg phasing,
reducing the number of free parameters.  Any two contralateral legs are
in antiphase at any time during motion (shifted in phase by half the
length of the standard cycle).  Mutual leg phasing in symmetrical gait,
for a six-legged device, is determined by two parameters, e.g., the
phase difference in motion of the middle leg and hindleg on one side
relative to the foreleg on the same side.

	Note that there exist gaits which, though not regular by our
definition, are symmetrical in the above sense.  The standard cycles for
the forelegs, middle legs and hindlegs may have retraction hases of
different duratins, but the retraction-protraction cycle for the right
and left legs of each pair must be the same and the full length of the
cycle for all pairs must be equal.  Naturally, contralateral legs must
remain in antiphase throughout motion.

	The above discussion was based on the assumption that the body of
the walking device is moving uniformly and rectilinearly, parallel to
a horizontal supporting plane.  In more complex cases some of our
concepts and statements remain valid, but others require modification.

	Consider motion of the device along an irregular but almost
horizontal surface.  As before, the motion of the body is assumed to be
horizontal, uniform and rectilinear.

	The definition of a regular gait remains valid, since it does not
involve the vertical coordinate of the point of contact, which may vary
from step to step on an irregular surface according to the topography
of the surface.  The same is true of the definition of a regular track.
The points of the track sequences need not lie on straight lines parallel
to the motion, but their projections on a horizontal plane do and they
are moreover equidistant.  The distance between the projections
of the successive track points of a leg is naturally defined as the track
span.  The length of the track span, thus defined, is again equal to the
displacement of the device over a full cycle.

	The definition of the supporting segment is retained, since the
height of the point of contact does not change during the retraction
phase.  The same holds for the definition of constructive span, and for the
relation between the constructive and track spans in a regular gait.

	In the general case, the lines joining the points of contact do not
form a plane polygon in a horizontal plane.  The static stability condition
remains valid if we define the supporting contour to be the convex hull
of the projections of the track points on the horizontal plane.  The
center of mass must also be projected onto this plane.

	In the next two sections we present the reesults of a kinematic
investigation of two mathematical models of six-legged walking devices.
The main purpose of the first model, T-1, was to serve as a tool in
working out methods for computerizing analysis of walking devices by
schematic on-line representation of the device on the computer display
and analysis of this representation, and also in working out a suitable
filming technique.  Motdl T-1 was used to implement synthesis algorithms
for the kinematics of the extremities in certain types of regular
gait, and the static stability of these gaits was studied.  We also
investigated simple forms of adaptation of the device to small
irregularities in the supporting surface.


	The second model, T-2, possessed a more sophisticated leg
kinematics, enabling the device to solve more complex motion
problems.  We investigated several variants of an algorithm for synthesis
of the track schedule, given the track and the motion of the body.  The
track may be irregular.  The kinematics of motion of the extremities is
subjected to the condition that the static stability reserve throughout
motion remain above a prescribed value.




2.  Investigation of model T-1
    --------------------------


	Model T-1 has six identical legs, arranged symmetrically, three
on each side of the body.  The distances between the fore and middle pair
and between the middle and hind pair were equal.  Each leg consisted of
two components -- thigh and shank -- and had two hinges, each with one
degree of freedom, one hinge in the shank and the other at the hip joint.
The axes of rotation of both hinges were horizontal and perpendicular to
the longitudinal axis of the body.  Each leg was able to move in a vertical
plane parallel to the body axis.

	The motion of the body was assumed to be uniform and rectilinear in
the direction of the longitudinal axis. which is in a horizontal position.

	It was assumed that the supporting topography was almost horizontal.
The topography was given as a cylindrical surface with horizontal
generators perpendicular to the direction of motion.  The small degree
of irregularity of the surface enabled the device to proceed along the
supporting surface while maintaining the body in a prescribed rectilinear
motion by using the adaptability of the legs to the terrain within limits
prescribed by the geometry of the legs and their kinematics.

	As mentioned in paragraph 1, in regular gait the projections of the
track points of each leg on the horizontal plane lie along a straight line
parallel to the motion of the device, forming thereon a sequence of
equidistant points.  The vertical coordinate of the track point is equal
to that of the supporting plane.

	Model T-1 was used to investigate a few types of regular gait and
to analyze the corresponding static stability reserve.

	In construction of the gaits we used the formal scheme proposed
by Wilson [14] to describe insect gaits.  The scheme is based on the idea
of waves of protractions.  Protraction of the hindleg triggers protraction
of the middle leg on the same side after a certain time lag, and the latter
in turn triggers protraction of the foreleg.  The hindlegs on both sides
are triggered alternately and protraction waves run periodically along
each side.
	Suppose that the length of the protraction phase is the same for all
legs and the time intervals between protractions of hindleg and middle leg,
on the one hand, and middle leg and foreleg, on the other, are equal,
the same for each side of the device.  Assume moreover that the relative
horizontal coordinates of the point of contact of each leg remain constant
from step to step.  Under these conditions, the gait of the device is
regular.  If the inter-protraction times for contralateral hindlegs are
equal, then the hidnlegs, hence also the middle legs and forelegs, are
always in antiphase; the gait is symmetrical.  If the interprotraction
times are different, contralateral legs do not alternate in phase and the
gait is asymmetrical.
i.
	We first consider symmetrical gaits of the above type.  The protraction
schedule may be characterized by three structural parameters: the time
interval